package Learn194;

public class TwoFur {
                            //二叉树查找
    //大的存右边 小的存左边
    //一样的不存
    //有极端情况 元素依次增大的话就全部存在右边 导致插入查找效率低

                            //平衡二叉树
    //任意节点左右子树高度差不能超过1
    //左旋
    //以不平衡的点作为支点
    //将根节点的右侧往左拉
    //右子节点变成新的父节点 多余的左子节点做降级的父节点的右子节点

    //右旋同理

                            //导致二叉树不平衡的四种情况
    //左左
    //根节点的左子树的左子树有节点插入时 就会导致二叉树不平衡
    //一次右旋

    //左右
    //根节点的左子树的右子树上 有节点插入
    //仅靠一次右旋不能解决
    //要先局部左旋一次变成左左的情况再进行一次右旋

    //右右 右左同理

                                //红黑树
    //自平衡的二叉查找树
    //72叫平衡二叉B树  78年-》红黑
    //是一种特殊的二叉查找树

    //每一个节点是红或者黑
    //不是高度平衡的 是根据红黑规则来的

    //1.每一个节点必须是红色或者黑色
    //2.根节点必须是黑色
    //3.一个节点没有子节点或者父节点，该节点相应的指针属性值为Nil，视为叶节点，叶节点是黑色
    //4.一个节点为红色那么它的子节点必须是黑色 不能出现红黑相连的情况
    //5.每一个节点 从他开始的所有后代节点的简单路径上 有相同数量的黑色节点

                                //添加节点规则
    //添加节点时 默认的颜色是红色

    //如果添加的是根节点 把颜色变成黑色

    //如果非根节点
    //父节点是黑色什么都不用做
    //父节点是红色 -叔叔节点是红色  父节点设置为黑色 叔叔设置为黑色 祖父设为红色  -祖父是根 变为黑色  -祖父非根 祖父设置为当前节点进行二次判断
    //            -叔叔节点是黑色-当前节点为父的右孩子  父节点设置为当前节点 左旋后（不考虑nil）再判断
    //            -             -当前节点为父的左孩子  父设成黑色 祖父变成红色 祖父为支点右旋






}
